package personal.learn.algorithm;

/**
 * 最大公约数
 *
 * @author Chai yansheng
 * @create 2019/8/28
 **/
public class MaximumCommonDivisor {
    /**
     * 一般方式求最大公约数
     * @param a
     * @param b
     * @return
     */
    public static int getMaximumCommonDivisor(int a, int b) {
        int min = a <= b ? a : b;
        int max = a >= b ? a : b;
        if (max % min == 0) {
            return max;
        }
        int maxCommonDivisor = 1;
        for (int i = 2; i < min / 2; i++) {
            if (max % i == 0 && min % i == 0) {
                maxCommonDivisor = i;
            }
        }
        return maxCommonDivisor;
    }

    /**
     * 辗转相除法
     * @param a
     * @param b
     * @return
     */
    public static int splitPhaseDivision(int a, int b) {
        int maxCommonDivisor = 1;
        int max = (a >= b ? a : b), min = (a <= b ? a : b);
        while (max % min != 0) {
            int t = max % min;
            max = min;
            min = t;
        }
        return maxCommonDivisor;
    }

    /**
     * 更相减损术
     * @param a
     * @param b
     * @return
     */
    public static int moreDestructive(int a, int b) {
        int max = (a >= b ? a : b), min = (a <= b ? a : b);
        while (max != min) {
            int t = max - min;
            max = (t >= min ? t : min);
            min = (t <= min ? t : min);
        }
        return min;
    }
    public static int gcd(int a ,int b) {
        if (a == b) {
            return a;
        }
        if (a < b) {
            return gcd(b, a);
        } else {
            //
        }
        return 0;
    }
    public static void main(String[] args) {
        int a = 1000, b = 1001;
        System.out.println(moreDestructive(a, b));
    }
}
